Abstract: Adleman [1] showed that deoxyribonucleic acid (DNA) strands could be employed towards calculating solutions to an instance of the Hamiltonian path problem (HPP). Lipton [5] also demonstrated that Adleman’s techniques could be used to solve the Satisfiability problem. In this paper, we use Adleman-Lipton model for developing a DNA algorithm to solve Maximum k-colourable Sub graph problem. In spite of the NP-hardness of Maximum k-colourable Sub graph problem our DNA procedures is done in a polynomial time.

Keywords: DNA computing, NP-hard problem, Maximum k-colourable Sub graph problem